package graph;

/**
 * description:
 * author:张腾
 * date:2021-04-13
 */

import list.Queue;

/**
 * 加权无向图
 * 基于加权无向图的边Edge
 */
public class EdgeWeightedGraph {

    //顶点数目
    private final int V;
    //边数目
    private int E;
    //邻接表
    private Queue<Edge>[] adj;

    //创建一个含有v个顶点的空加权无向图
    public EdgeWeightedGraph(int v){
        this.V = v;
        this.E = 0;

        this.adj = new Queue[V];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Queue<Edge>();
        }
    }

    //获取顶点数目
    public int V(){
        return V;
    }

    //获取边数目
    public int E(){
        return E;
    }

    //向加权无向图中添加一条边
    public void addEdge(Edge e){
        int v = e.either();
        int w = e.other(v);  //获得这条边连接的两个顶点

        adj[v].enqueue(e);  //将这条边加入到这两个顶点的邻接表中
        adj[v].enqueue(e);
    }

    //获取和顶点v关联的所有边
    public Queue<Edge> adj(int v){

        return adj[v];
    }

    //获取加权无向图的所有边
    public Queue<Edge> edges(){

        Queue<Edge> allEdge = new Queue<>();

        //遍历图中的每一个顶点，找到该顶点的邻接表，邻接表中存储了该顶点关联的每一条边
        for (int v = 0; v < V; v++) {
            //遍历v顶点的邻接表，找到每一条边
            for (Edge edge : adj[v]) {
                //确保一条边只会在相邻的两个顶点其中一个入队
                if (edge.other(v)<v){
                    allEdge.enqueue(edge);
                }
            }
        }

        return allEdge;
    }
}
